package com.niuke;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * 2. 任务最优调度
 * 题目描述参考下面链接，类似力扣 621. 任务调度器
 * https://blog.csdn.net/m0_46181452/article/details/131666800
 */
public class NiukeMoni5nan {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> tasks = new ArrayList<>();
        String stepStr = scanner.next();
        String[] stepTmp = stepStr.split(",");
        for (String step : stepTmp) {
            tasks.add(Integer.parseInt(step));
        }

        int cd = scanner.nextInt();

        System.out.println(leastInterval(tasks.toArray(new Integer[0]), cd));
    }

    public static int leastInterval(Integer[] tasks, int n) {

        // 给各类型任务计次
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (Integer ch : tasks) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }

        // 任务类型总数
        int m = freq.size();

        /**
         * 这两个集合很关键，大小都是固定的。
         * 一个记录因冷却最早可以执行该类型任务的有效时间，初始都为1。
         * 一个记录该类型任务的剩余次数。
         */
        List<Integer> nextValid = new ArrayList<>();
        List<Integer> rest = new ArrayList<>();
        Set<Map.Entry<Integer, Integer>> entrySet = freq.entrySet();
        for (Map.Entry<Integer, Integer> entry : entrySet) {
            int value = entry.getValue();
            nextValid.add(1);
            rest.add(value);
        }

        int time = 0;
        for (int i = 0; i < tasks.length; ++i) {
            ++time;
            int minNextValid = Integer.MAX_VALUE;
            for (int j = 0; j < m; ++j) {
                if (rest.get(j) != 0) {
                    minNextValid = Math.min(minNextValid, nextValid.get(j));
                }
            }
            time = Math.max(time, minNextValid);
            int best = -1;
            for (int j = 0; j < m; ++j) {
                /**
                 * 挑选有效时间小于等于当前 time 的，并且剩余数量最多的任务。
                 * 如果有好几个最多的，取第一个就行，要完全大于才能排到最优。
                 * 剩下的必要条件不要忽略：次数不能为0 和 best一开始-1的设置。
                 */
                if (rest.get(j) != 0 && nextValid.get(j) <= time) {
                    if (best == -1 || rest.get(j) > rest.get(best)) {
                        best = j;
                    }
                }
            }
            nextValid.set(best, time + n + 1); // 更新最优执行任务的下次可能执行时间
            rest.set(best, rest.get(best) - 1); // 减少最优执行任务的次数
        }

        return time;
    }

}
